#define _CRT_SECURE_NO_WARNINGS
#include "Queue.h"

void QueueInit(Queue* q)
{
	assert(q);
	q->front = q->rear = NULL;
}
void QueuePush(Queue* q, QDataType data)
{
	assert(q);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if(!newnode)
	{
		perror("malloc fail");
		exit(-1);
	}
	else
	{
		newnode->data = data;
		newnode->next = NULL;
	}

	if (q->rear == NULL)
	{
		q->front = q->rear = newnode;
	}
	else
	{
		q->rear->next = newnode;
		q->rear = newnode;
	}
}

void QueuePop(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));

	if (q->front->next == NULL)
	{
		free(q->rear);
		q->rear = q->front = NULL;
	}
	else
	{
		QNode* del = q->front;
		q->front = del->next;
		free(del);
		del = NULL;
	}
}

int QueueEmpty(Queue* q)
{
	assert(q);
	return q->front == NULL && q->rear == NULL;
}
void QueueDestroy(Queue* q)
{
	assert(q);
	QNode* cur = q->front;
	while (cur)
	{
		QNode* del = cur;
		cur = cur->next;
		free(del);
	}
	q->front = q->rear = NULL;
}

int QueueSize(Queue* q)
{
	assert(q);
	if (QueueEmpty(q) == 0)
	{
		return 0;
	}
	else
	{
		QNode* cur = q->front;
		int count = 0;
		while (cur)
		{
			cur = cur->next;
			count++;
		}
		return count;
	}
}
QDataType QueueFront(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));

	return q->front->data;
}
QDataType QueueBack(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));

	return q->rear->data;
}

MyStack* myStackCreate() {

	MyStack* obj = (MyStack*)malloc (sizeof(MyStack));
	QueueInit(&obj->q1);
	QueueInit(&obj->q2);
	return obj;
}

void myStackPush(MyStack* obj, int x) {
	if (QueueEmpty(&obj->q1))
	{
		QueuePush(&obj->q1, x);
	}
	else
	{
		QueuePush(&obj->q2, x);
	}
}

int myStackPop(MyStack* obj) {
	Queue* empty = &obj->q1;
	Queue* noneEmpty = &obj->q2;
	if (QueueEmpty(&obj->q1) == 0)
	{
		empty = &obj->q2;
		noneEmpty = &obj->q1;
	}
	while(QueueSize(noneEmpty)>1)
	{
		QueuePush(empty, QueueFront(noneEmpty));
		QueuePop(noneEmpty);
	}
	int top = QueueFront(noneEmpty);
	QueuePop(noneEmpty);
	return top;
}

int myStackTop(MyStack* obj) {
	if (QueueEmpty(&obj->q1) )
	{
		return QueueBack(&obj->q1);
	}
	else
	{
		return QueueBack(&obj->q2);
	}
}

bool myStackEmpty(MyStack* obj) {
	return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}

void myStackFree(MyStack* obj) {
	QueueDestroy(&obj->q1);
	QueueDestroy(&obj->q2);
	free(obj);
}
